<head>
    <meta charset="UTF-8">
<title>历届试题 斐波那契</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <div>[问题描述]</div>
<div>&nbsp; &nbsp; 斐波那契数列大家都非常熟悉。它的定义是：</div>
<div>&nbsp;</div>
<div>&nbsp; &nbsp; f(x) = 1 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;.... (x=1,2)</div>
<div>&nbsp; &nbsp; f(x) = f(x-1) + f(x-2) &nbsp; &nbsp; &nbsp;.... (x&gt;2)</div>
<div>&nbsp;</div>
<div>&nbsp; &nbsp; 对于给定的整数 n 和 m，我们希望求出：</div>
<div>&nbsp; &nbsp; f(1) + f(2) + ... + f(n) &nbsp;的值。但这个值可能非常大，所以我们把它对 f(m) 取模。</div>
<div>&nbsp; &nbsp; 公式如下</div>
<div><img src="http://lx.lanqiao.cn/RequireFile.do?fid=hyry39mn" width="302" height="78" alt="" /></div>
<div>&nbsp;</div>
<div>&nbsp; &nbsp; 但这个数字依然很大，所以需要再对 p 求模。</div>
<div>&nbsp;</div>
<div>【输入格式】</div>
<div>输入为一行用空格分开的整数 n m p (0 &lt; n, m, p &lt; 10^18)</div>
<div>&nbsp;</div>
<div>【输出格式】</div>
<div>输出为1个整数，表示答案</div>
<div>&nbsp;</div>
<div>【样例输入】</div>
<div>2 3 5</div>
<div>【样例输出】</div>
<div>0</div>
<div>&nbsp;</div>
<div>【样例输入】</div>
<div>15 11 29</div>
<div>【样例输出】</div>
<div>25</div>
<div>&nbsp;</div>